package com.sicheng.蓝桥.国赛准备.第十三届JavaB;

import java.util.Scanner;

/**
 * @author zsc
 * @version 1.0
 * @date 2022/6/18 10:59
 */
public class G背包与魔法 {
    /**
     * 【问题描述】
     * 小蓝面前有 N 件物品，其中第 i 件重量是 Wi，价值是 Vi。她还有一个背
     * 包，最大承重是 M。
     * 小蓝想知道在背包称重范围内，她最多能装总价值多少的物品？
     * 特别值得一提的是，小蓝可以使用一个魔法，将一件物品的重量增加 K，
     * 同时价值翻倍。(当然小蓝也可以不使用魔法）
     * 【输入格式】
     * 第一行包含 3 个整数 N、M 和 K。
     * 以下 N 行，每行两个整数 Wi 和 Vi。
     * 【输出格式】
     * 一个整数代表答案。
     * 【样例输入】
     * 3 10 3
     * 5 10
     * 4 9
     * 3 8
     * 【样例输出】
     * 26
     * 【样例说明】
     * 选择第二件和第三件物品，同时对第二件物品使用魔法。
     * 试题 G: 背包与魔法 13
     * 第十三届蓝桥杯大赛软件赛决赛 Java 大学 B 组
     * 【评测用例规模与约定】
     * 对于 30% 的数据，1 ≤ N, M, K ≤ 100.
     * 对于 100% 的数据，1 ≤ N ≤ 2000, 1 ≤ M, K ≤ 10000, 0 ≤ Wi, Vi ≤ 10000
     */
    public static void main(String[] args) {

        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int m = scanner.nextInt();
        int k = scanner.nextInt();
        long[] dp = new long[m + 1];
        int[] state = new int[m + 1];
        int[] w = new int[n];
        int[] v = new int[n];
        for (int i = 0; i < n; i++) {
            w[i] = scanner.nextInt();
            v[i] = scanner.nextInt();
        }

        for (int i = 0; i < n; i++) {
            for (int j = m; j >= w[i]; j--) {
                long value = dp[j - w[i]] + v[i];
                if (value > dp[j]) {
                    dp[j] = value;
                    //压缩状态 记录当前选择的情况  如010表示选择w[1],111表示选择w[0],w[1],w[2]
                    state[j] = (1 << i) | state[j - w[i]];
                }
            }
        }

        long max = dp[m];

        for (int i = m - k; i >= 1; i--) {
            //选择一个物品施加魔法
            //是否可以施加
            for (int j = 0; j < n; j++) {
                if ((state[i] >> j & 1) == 1) {
                    max = Math.max(max, dp[i] + v[j]);
                }
            }
        }

        System.out.println(max);
    }
}
